package test3;

public class Solution7 {
    class ProductOfNumbers {

        public ProductOfNumbers() {

        }

        public void add(int num) {

        }

        public int getProduct(int k) {
             return 0;
        }
    }


    class NumArray {

        int[] nums;
        int[] values;
        int len;

        public NumArray(int[] nums) {
            this.nums = nums;
            this.len = nums.length;
            values = new int[len * 2];
            add(0, 0, len - 1);
        }

        public int add(int pos, int left, int right) {
            if (left == right) {
                values[pos] = nums[left];
                return nums[left];
            }
            int mid = (right + left) /2;
            int leftVal = add(2 * pos + 1, left, mid);
            int rightVal = add(2 * pos + 2, mid + 1, right);
            values[pos] = leftVal + rightVal;
            return values[pos];
        }


        public void update(int i, int val) {
            nums[i] = val;
            update(i, 0, 0, len-1, val);
        }

        public int update(int i, int pos, int left, int right, int val) {

            if (i < left || i > right) {
                return 0;
            }
            if (left == right) {
                values[pos] = val;
                return val;
            }
            int mid = (left + right) / 2;
            int leftVal = update(i, 2 * pos + 1, left, mid, val);
            int rightVal = update(i, 2 * pos + 2, mid + 1, right, val);
            values[pos] = leftVal + rightVal;
            return values[pos];
        }

        public int sumRange(int i, int j) {
            return sumRange(i, j, 0, len - 1, 0);
        }

        public int sumRange(int tarLeft, int tarRight, int left, int right, int pos) {

            if (tarLeft == left && tarRight == right) {
                return values[pos];
            }
            if (tarLeft > right || tarRight < left) {
                return 0;
            }

            int mid = (left + right) / 2;
            int leftValue = sumRange(tarLeft, Math.min(tarRight, mid), left, mid, 2 * pos + 1);
            int rightValue = sumRange(Math.max(tarLeft, mid), tarRight, mid + 1, right, 2 * pos + 2);

            return leftValue + rightValue;
        }
    }

    /*class NumArray2 {
        private int[] b;
        private int len;
        private int[] nums;

        public NumArray2(int[] nums) {
            this.nums = nums;
            double l = Math.sqrt(nums.length);
            len = (int) Math.ceil(nums.length / l);
            b = new int[len];
            for (int i = 0; i < nums.length; i++)
                b[i / len] += nums[i];
        }

        public int sumRange(int i, int j) {
            int sum = 0;
            int startBlock = i / len;
            int endBlock = j / len;
            if (startBlock == endBlock) {
                for (int k = i; k <= j; k++)
                    sum += nums[k];
            } else {
                for (int k = i; k <= (startBlock + 1) * len - 1; k++)
                    sum += nums[k];
                for (int k = startBlock + 1; k <= endBlock - 1; k++)
                    sum += b[k];
                for (int k = endBlock * len; k <= j; k++)
                    sum += nums[k];
            }
            return sum;
        }

        public void update(int i, int val) {
            int b_l = i / len;
            b[b_l] = b[b_l] - nums[i] + val;
            nums[i] = val;
        }

    }*/

}
